from collections import defaultdict
from typing import List
"""思路：
1. 滑动窗口 + 哈希表计数
由于 words 中的单词长度相同（假设为 L），我们可以采用滑动窗口的方法，
每次检查 s 中长度为 L 的子串是否匹配 words 中的单词，并统计它们的出现次数是否一致。
"""

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        # 计算单个单词长度和总单词数
        word_len = len(words[0])  # 每个单词的长度都相同
        word_cnt = len(words)  # 单词列表中的单词总数
        n = len(s)  # 字符串s的总长度

        # 如果字符串长度不足以容纳所有单词，直接返回空列表
        if n < word_len * word_cnt:
            return []

        ans = []  # 存储结果的列表

        # 创建目标单词计数器（记录每个单词应该出现的次数）
        tgt_cntr = defaultdict(int)
        for w in words:
            tgt_cntr[w] += 1

        # 遍历所有可能的起始位置（0到word_len-1）
        for start in range(word_len):
            cur_cntr = defaultdict(int)  # 当前窗口的单词计数器
            left = start  # 滑动窗口的左边界
            cnt = 0  # 当前窗口中有效单词的计数

            # 滑动窗口，每次移动一个单词的长度
            for right in range(start, n, word_len):
                # 获取当前单词
                w = s[right: right + word_len]

                # 如果当前单词在目标单词中
                if w in tgt_cntr:
                    cur_cntr[w] += 1  # 增加当前单词计数
                    cnt += 1  # 增加有效单词总数

                    # 如果当前单词出现次数超过目标次数，移动左边界
                    while cur_cntr[w] > tgt_cntr[w]:
                        left_w = s[left: left + word_len]  # 获取左边界的单词
                        cur_cntr[left_w] -= 1  # 减少该单词计数
                        cnt -= 1  # 减少有效单词总数
                        left += word_len  # 移动左边界

                    # 如果找到满足条件的子串，记录起始位置
                    if cnt == word_cnt:
                        ans.append(left)
                else:
                    # 遇到无效单词，重置窗口
                    left = right + word_len
                    cur_cntr.clear()
                    cnt = 0

        return ans